A fast recursive algorithm for computing the discrete cosine transform can be used for image data compression that is useful in compressing data for either data storage for saving storage space or for data communications for saving communication channel bandwidth. During the calculation of the discrete cosine transform the DCT algorithm separates and combines data. A Radix-2 DCT separate block process and a Radix-2 DCT combine block process have been used to separate and combine data blocks. This DCT does not enable one to directly merge two equal sized transforms into one double size transform, nor to split double size transform whole. Equal splitting and merging is desirable for communicating transformed packets in smaller divisible packets. However, the DCT is not a true merge and split transformation process. The DCT data have been quantized into integers for converting into binary codes and causing data loss. When the DCT is used to split or merge there is a lossy transformation as there is no teachings known to form a mirror DCT transform that offer lossless transformation. A problem with the DCT transform is that the DCT can only perform a merge process by inversely transforming two equal sized DCT transforms back into the time domain, and then merge in the time domain, and finally forward transform the combined double size block into a double size DCT transform. This disadvantageously required additional inverse transformations and forward transformations prior to transmission that degrades the transformed data when repetively inverse and forward transforming the data. Hence, the DCT is not a true direct split or merge transform. Another problem with this discrete cosine transform is that there is no decimation-in-time DCT combine flow process compatible with the DCT decimation-in-time separate flow process. In prior art the T(N/2), type-II DCT and D(N/2) type-IV DCT blocks are DCT transforms of equal sized blocks processing first and second halves of the input data prior to combining the two halves into a double size type-II DCT output. The separate transform of prior art operates on first and second half inputs but the data is transformed into odd and even type-II DCT halves, incompatible with true merge and split transform processing. During the separate transformation processing of prior art the first and second half data are firstly subject to add and subtract processing prior to transformation, that is, separate combinational processing precedes the forward transformations. Another disadvantage of type-II and type-IV DCTs is that the separate and combine processes are always incurred with loss of data integrity. The type-II DCT are lossy separate and combine processes. Improved type-II and type-IV DCT provide lossy split and merge processes where the splitting and merging are mutually compatible for true splitting and merging of transform data in the transform domain, but disadvantageously provide lossy transformations.
A 2×2 rotator, whether lossy or lossless, has two bit-parallel serial word inputs X1 and X2 that are rotated in radians into two outputs Y1 and Y2. The first output of the 2×2 rotator is the first input weighted by the cosine of the rotating angle adding to the second input weighted by the sine of the same rotating angle. The second output of a 2×2 rotator is the first input weighted by the sine of the same rotating angle subtracted from the second input weighted by the cosine of the same rotating angle. That is, Y1=cos θX1+sin θX2 and Y2=−sin θX1+cos θX2. An integer lossy 2×2 rotator has two integer outputs for two integer inputs. An integer lossy 2×2 rotator has been implemented using traditional lifting stages. The unweighted input in each lifting stage is always used for addition but not for subtraction. Rotators have been used in DCT transforms. Rounding errors cannot be cancelled during continuous use of additions in lifting stages. The total rounding error of the traditional lifting method used in prior arts is very large because the accumulation of rounding errors throughout lifting stages. As such, the use of traditional lifting method produces lossy rotators.
The progressive transmission of compressed data works well when the data packets are sent and received without any error or loss. But when a packet is lost, the long delay in receiving a retransmitted packet often causes stalls in the whole decompression process. To improve the data integrity in unreliable channels, the original data stream has been split and sent on two separate links. Early multiple description speech coding processes separate the data into even and odd parts, and compress and communicate the even and odd parts over two independent paths. However, there are two drawbacks in multiple description methods. A first disadvantage is the use of separate compression and decompression hardware with the use of two independent channels. A second disadvantage is the respective inefficient compression of even and odd parts of data because the correlation between adjacent data samples in each part has been decreased. Recent multiple description methods add redundancies to the two halves of compressed data. The method of adding statistical dependencies to each channel can be used to estimate the loss of description. However, the method of adding statistical dependencies is not a real-time operation. Statistical data are needed to generate the multiple description transform in real time. The derived benefit of multiple descriptions may not be able to justify the additional complexity.
Another problem associated with transmitting DCT compressed data using unreliable communication links is the unreliable reconstruction of the compressed image after reception. Compressed still images or compressed video frames are to be transmitted over unreliable links. When one of the communication links is functional but the remaining communication links are corrupted, the existing DCT reconstruction disadvantageously poorly reconstructs the low-resolution version of the original image. When more links are functional, the reconstructed image quality could be improved at the cost of adding addition communication channels. Another problem with DCT transform communications is the incompatibility of receiver resolution. When a digital high-definition TV picture is transmitted to receivers, a conventional analog TV receiver must first decompress the high-definition picture signal prior to performing resolution down conversion for display. A low-resolution down conversion of compressed data has a less amount of data and save processing power and can be used to display an image on a low-resolution display but suffers from having to first decompress the high-resolution data before displaying the low-resolution data. These and other disadvantages are solved or reduced using the invention.